#include "dfs.h"
#include <cstdio>
#include "Coordinate.h"
#include "Map.h"

const int directX[4] = {-1, 0, 1, 0}, directY[4] = {0, 1, 0, -1};
//extern const int directX[4], directY[4];

const char *get_dir(Coord<int> &start, Coord<int> &end)
{
    int dx = end.x() - start.x(), dy = end.y() - start.y();
    if (dx == -1 && dy == 0)
        return "up";
    else if (dx == 0 && dy == 1)
        return "right";
    else if (dx == 1 && dy == 0)
        return "down";
    else if (dx == 0 && dy == -1)
        return "left";
    else return "ERROR!!!";
}

void print_path_dfs(Stack<Coord<int> > &path)
{
    Coord<int> top = path.pop();
    int sx = top.x();
    int sy = top.y();
    printf("START\n");
    while (!path.empty()) {
        Coord<int> end = path.pop();
        int ex = end.x();
        int ey = end.y();
        printf("From(%d, %d) %s to (%d, %d)\n", sx, sy, get_dir(top, end), ex, ey);
        sx = ex, sy = ey;
        top = end;
    }
    printf("END\n");
}

void reverse_stack(Stack<Coord<int> > &src, Stack<Coord<int> > &des)
{
    while (!src.empty())
        des.push(src.pop());
}

bool dfs(Coord<int> const &curr,
         Coord<int> const &end,
         Stack<Coord<int> > &stk,
         Map<int> &visited,
         Map<int> const &maze)
{
    visited.val(curr.y(), curr.x(), true);
    stk.push(curr);
    if (curr == end) {
        Stack<Coord<int> > tmp;
        reverse_stack(stk, tmp);
        print_path_dfs(tmp);
        return true;
    }
    for (int i = 0; i < 4; i++) {
        int x = curr.x() + directX[i], y = curr.y() + directY[i];
        Coord<int> coord(x, y);

        if (x < 0 || x >= maze.rows() || y < 0 || y >= maze.cols())
            continue;
        if (maze.val(y, x) || visited.val(y, x))
            continue;
        if (dfs(coord, end, stk, visited, maze))
            return true;
    }
    return false;
}